home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 002 / emacssrc.arc / SEARCH.C < prev    next >
C/C++ Source or Header  |  1987-01-12  |  32KB  |  1,372 lines
  1. /*
  2.  * The functions in this file implement commands that search in the forward
  3.  * and backward directions.  There are no special characters in the search
  4.  * strings.  Probably should have a regular expression search, or something
  5.  * like that.
  6.  *
  7.  * Aug. 1986 John M. Gamble:
  8.  *    Made forward and reverse search use the same scan routine.
  9.  *
  10.  *    Added a limited number of regular expressions - 'any',
  11.  *    'character class', 'closure', 'beginning of line', and
  12.  *    'end of line'.
  13.  *
  14.  *    Replacement metacharacters will have to wait for a re-write of
  15.  *    the replaces function, and a new variation of ldelete().
  16.  *
  17.  *    For those curious as to my references, i made use of
  18.  *    Kernighan & Plauger's "Software Tools."
  19.  *    I deliberately did not look at any published grep or editor
  20.  *    source (aside from this one) for inspiration.  I did make use of
  21.  *    Allen Hollub's bitmap routines as published in Doctor Dobb's Journal,
  22.  *    June, 1985 and modified them for the limited needs of character class
  23.  *    matching.  Any inefficiences, bugs, stupid coding examples, etc.,
  24.  *    are therefore my own responsibility.
  25.  */
  26.  
  27. #include        <stdio.h>
  28. #include    "estruct.h"
  29. #include        "edef.h"
  30. #include    "esearch.h"
  31.  
  32. /*
  33.  * Reversed pattern array.
  34.  */
  35. char    tap[NPAT];
  36.  
  37. #if    MAGIC
  38. /*
  39.  * The variable magical determines if there are actual
  40.  * metacharacters in the string - if not, then we don't
  41.  * have to use the slower MAGIC mode search functions.
  42.  *
  43.  * The variable mclen holds the length of the matched
  44.  * string - used by the replace functions.
  45.  *
  46.  * The arrays mcpat and tapcm hold the MC and reversed
  47.  * MC search structures.
  48.  */
  49. short int    magical = FALSE;
  50. int        mclen = 0;
  51. MC        mcpat[NPAT];
  52. MC        tapcm[NPAT];
  53. #endif
  54.  
  55. /*
  56.  * forwsearch -- Search forward.  Get a search string from the user, and
  57.  *    search, beginning at ".", for the string.  If found, reset the "."
  58.  *    to be just after the match string, and (perhaps) repaint the display.
  59.  */
  60.  
  61. forwsearch(f, n)
  62. {
  63.     register int status = TRUE;
  64.  
  65.     /* Resolve the repeat count.
  66.      */
  67.     if (n == 0)
  68.         n = 1;
  69.  
  70.     /* If n is negative, search backwards.
  71.      * Otherwise proceed by asking for the search string.
  72.      */
  73.     if (n < 0)
  74.         status = backsearch(f, -n);
  75.  
  76.     /* Ask the user for the text of a pattern.  If the
  77.      * response is TRUE (responses other than FALSE are
  78.      * possible), search for the pattern.
  79.      */
  80.     else if ((status = readpattern("Search", &pat[0], TRUE)) == TRUE)
  81.     {
  82.         do
  83.         {
  84. #if    MAGIC
  85.             if ((magical && curwp->w_bufp->b_mode & MDMAGIC) != 0)
  86.                 status = mcscanner(&mcpat[0], FORWARD, PTEND);
  87.             else
  88. #endif
  89.                 status = scanner(&pat[0], FORWARD, PTEND);
  90.         } while ((--n > 0) && status);
  91.  
  92.         /* ...and complain if not there.
  93.          */
  94.         if (status == FALSE)
  95.             mlwrite("Not found");
  96.     }
  97.     return(status);
  98. }
  99.  
  100. /*
  101.  * forwhunt -- Search forward for a previously acquired search string,
  102.  *    beginning at ".".  If found, reset the "." to be just after
  103.  *    the match string, and (perhaps) repaint the display.
  104.  */
  105.  
  106. forwhunt(f, n)
  107. {
  108.     register int status = TRUE;
  109.  
  110.     /* Resolve the repeat count.
  111.      */
  112.     if (n == 0)
  113.         n = 1;
  114.     else if (n < 0)        /* search backwards */
  115.         return(backhunt(f, -n));
  116.  
  117.     /* Make sure a pattern exists, or that we didn't switch
  118.      * into MAGIC mode until after we entered the pattern.
  119.      */
  120.     if (pat[0] == '\0')
  121.     {
  122.         mlwrite("No pattern set");
  123.         return FALSE;
  124.     }
  125. #if    MAGIC
  126.     if ((curwp->w_bufp->b_mode & MDMAGIC) != 0 &&
  127.          mcpat[0].mc_type == MCNIL)
  128.     {
  129.         if (!mcstr())
  130.             return FALSE;
  131.     }
  132. #endif
  133.  
  134.     /* Search for the pattern...
  135.      */
  136.     do
  137.     {
  138. #if    MAGIC
  139.         if ((magical && curwp->w_bufp->b_mode & MDMAGIC) != 0)
  140.             status = mcscanner(&mcpat[0], FORWARD, PTEND);
  141.         else
  142. #endif
  143.             status = scanner(&pat[0], FORWARD, PTEND);
  144.     } while ((--n > 0) && status);
  145.  
  146.     /* ...and complain if not there.
  147.      */
  148.     if (status == FALSE)
  149.         mlwrite("Not found");
  150.  
  151.     return(status);
  152. }
  153.  
  154. /*
  155.  * backsearch -- Reverse search.  Get a search string from the user, and
  156.  *    search, starting at "." and proceeding toward the front of the buffer.
  157.  *    If found "." is left pointing at the first character of the pattern
  158.  *    (the last character that was matched).
  159.  */
  160. backsearch(f, n)
  161. {
  162.     register int status = TRUE;
  163.  
  164.     /* Resolve null and negative arguments.
  165.      */
  166.     if (n == 0)
  167.         n = 1;
  168.  
  169.     /* If n is negative, search forwards.
  170.      * Otherwise proceed by asking for the search string.
  171.      */
  172.     if (n < 0)
  173.         status = forwsearch(f, -n);
  174.  
  175.     /* Ask the user for the text of a pattern.  If the
  176.      * response is TRUE (responses other than FALSE are
  177.      * possible), search for the pattern.
  178.      */
  179.     else if ((status = readpattern("Reverse search", &pat[0], TRUE)) == TRUE)
  180.     {
  181.         do
  182.         {
  183. #if    MAGIC
  184.             if ((magical && curwp->w_bufp->b_mode & MDMAGIC) != 0)
  185.                 status = mcscanner(&tapcm[0], REVERSE, PTBEG);
  186.             else
  187. #endif
  188.                 status = scanner(&tap[0], REVERSE, PTBEG);
  189.         } while ((--n > 0) && status);
  190.  
  191.         /* ...and complain if not there.
  192.          */
  193.         if (status == FALSE)
  194.             mlwrite("Not found");
  195.     }
  196.     return(status);
  197. }
  198.  
  199. /*
  200.  * backhunt -- Reverse search for a previously acquired search string,
  201.  *    starting at "." and proceeding toward the front of the buffer.
  202.  *    If found "." is left pointing at the first character of the pattern
  203.  *    (the last character that was matched).
  204.  */
  205. backhunt(f, n)
  206. {
  207.     register int    status = TRUE;
  208.  
  209.     /* Resolve null and negative arguments.
  210.      */
  211.     if (n == 0)
  212.         n = 1;
  213.     else if (n < 0)
  214.         return(forwhunt(f, -n));
  215.  
  216.     /* Make sure a pattern exists, or that we didn't switch
  217.      * into MAGIC mode until after we entered the pattern.
  218.      */
  219.     if (tap[0] == '\0')
  220.     {
  221.         mlwrite("No pattern set");
  222.         return FALSE;
  223.     }
  224. #if    MAGIC
  225.     if ((curwp->w_bufp->b_mode & MDMAGIC) != 0 &&
  226.          tapcm[0].mc_type == MCNIL)
  227.     {
  228.         if (!mcstr())
  229.             return FALSE;
  230.     }
  231. #endif
  232.  
  233.     /* Go search for it...
  234.      */
  235.     do
  236.     {
  237. #if    MAGIC
  238.         if ((magical && curwp->w_bufp->b_mode & MDMAGIC) != 0)
  239.             status = mcscanner(&tapcm[0], REVERSE, PTBEG);
  240.         else
  241. #endif
  242.             status = scanner(&tap[0], REVERSE, PTBEG);
  243.     } while ((--n > 0) && status);
  244.  
  245.     /* ...and complain if not there.
  246.      */
  247.     if (status == FALSE)
  248.         mlwrite("Not found");
  249.  
  250.     return(status);
  251. }
  252.  
  253. #if    MAGIC
  254. /*
  255.  * mcscanner -- Search for a meta-pattern in either direction.
  256.  */
  257. int    mcscanner(mcpatrn, direct, beg_or_end)
  258. MC    *mcpatrn;        /* pointer into pattern */
  259. int    direct;        /* which way to go.*/
  260. int    beg_or_end;    /* put point at beginning or end of pattern.*/
  261. {
  262.     register LINE *lastline;    /* last line position during scan */
  263.     register int lastoff;        /* position within last line */
  264.     LINE *curline;            /* current line during scan */
  265.     int curoff;            /* position within current line */
  266.     int c;                /* (dummy) char at current position */
  267.  
  268.     /* If we are going in reverse, then the 'end' is actually
  269.      * the beginning of the pattern.  Toggle it.
  270.      */
  271.     beg_or_end ^= direct;
  272.  
  273.     /* Setup local scan pointers to global ".".
  274.      */
  275.     curline = curwp->w_dotp;
  276.     curoff  = curwp->w_doto;
  277.  
  278.     /* Scan each character until we hit the head link record.
  279.      */
  280.     while (!boundry(curline, curoff, direct))
  281.     {
  282.         /* Save the current position in case we need to
  283.          * restore it on a match, and initialize mclen to
  284.          * zero in case we are doing a search for replacement.
  285.          */
  286.         lastline = curline;
  287.         lastoff = curoff;
  288.         mclen = 0;
  289.  
  290.         if (amatch(mcpatrn, direct, &curline, &curoff))
  291.         {
  292.             /* A SUCCESSFULL MATCH!!!
  293.              * reset the global "." pointers.
  294.              */
  295.             if (beg_or_end == PTEND)    /* at end of string */
  296.             {
  297.                 curwp->w_dotp = curline;
  298.                 curwp->w_doto = curoff;
  299.             }
  300.             else        /* at beginning of string */
  301.             {
  302.                 curwp->w_dotp = lastline;
  303.                 curwp->w_doto = lastoff;
  304.             }
  305.  
  306.             curwp->w_flag |= WFMOVE; /* flag that we have moved */
  307.             return TRUE;
  308.         }
  309.  
  310.         /* Advance the cursor.
  311.          */
  312.         c = nextch(&curline, &curoff, direct);
  313.     }
  314.  
  315.     return FALSE;    /* We could not find a match.*/
  316. }
  317.  
  318. /*
  319.  * amatch -- Search for a meta-pattern in either direction.  Based on the
  320.  *    recursive routine amatch() (for "anchored match") in
  321.  *    Kernighan & Plauger's "Software Tools".
  322.  */
  323. static int    amatch(mcptr, direct, pcwline, pcwoff)
  324. register MC    *mcptr;    /* string to scan for */
  325. int        direct;        /* which way to go.*/
  326. LINE        **pcwline;    /* current line during scan */
  327. int        *pcwoff;    /* position within current line */
  328. {
  329.     register int c;            /* character at current position */
  330.     LINE *curline;            /* current line during scan */
  331.     int curoff;            /* position within current line */
  332.     int nchars;
  333.  
  334.     /* Set up local scan pointers to ".", and get
  335.      * the current character.  Then loop around
  336.      * the pattern pointer until success or failure.
  337.      */
  338.     curline = *pcwline;
  339.     curoff = *pcwoff;
  340.  
  341.     /* The beginning-of-line and end-of-line metacharacters
  342.      * do not compare against characters, they compare
  343.      * against positions.
  344.      * BOL is guaranteed to be at the start of the pattern
  345.      * for forward searches, and at the end of the pattern
  346.      * for reverse searches.  The reverse is true for EOL.
  347.      * So, for a start, we check for them on entry.
  348.      */
  349.     if (mcptr->mc_type == BOL)
  350.     {
  351.         if (curoff != 0)
  352.             return FALSE;
  353.         mcptr++;
  354.     }
  355.  
  356.     if (mcptr->mc_type == EOL)
  357.     {
  358.         if (curoff != llength(curline))
  359.             return FALSE;
  360.         mcptr++;
  361.     }
  362.  
  363.     while (mcptr->mc_type != MCNIL)
  364.     {
  365.         c = nextch(&curline, &curoff, direct);
  366.  
  367.         if (mcptr->mc_type & CLOSURE)
  368.         {
  369.             /* Try to match as many characters as possible
  370.              * against the current meta-character.  A
  371.              * newline never matches a closure.
  372.              */
  373.             nchars = 0;
  374.             while (c != '\n' && mceq(c, mcptr))
  375.             {
  376.                 c = nextch(&curline, &curoff, direct);
  377.                 nchars++;
  378.             }
  379.  
  380.             /* We are now at the character that made us
  381.              * fail.  Try to match the rest of the pattern.
  382.              * Shrink the closure by one for each failure.
  383.              * Since closure matches *zero* or more occurences
  384.              * of a pattern, a match may start even if the
  385.              * previous loop matched no characters.
  386.              */
  387.             mcptr++;
  388.  
  389.             for (;;)
  390.             {
  391.                 c = nextch(&curline, &curoff, direct ^ REVERSE);
  392.  
  393.                 if (amatch(mcptr, direct, &curline, &curoff))
  394.                 {
  395.                     mclen += nchars;
  396.                     goto success;
  397.                 }
  398.  
  399.                 if (nchars-- == 0)
  400.                     return FALSE;
  401.             }
  402.         }
  403.         else            /* Not closure.*/
  404.         {
  405.             /* The only way we'd get a BOL metacharacter
  406.              * at this point is at the end of the reversed pattern.
  407.              * The only way we'd get an EOL metacharacter
  408.              * here is at the end of a regular pattern.
  409.              * So if we match one or the other, and are at
  410.              * the appropriate position, we are guaranteed success
  411.              * (since the next pattern character has to be MCNIL).
  412.              * Before we report success, however, we back up by
  413.              * one character, so as to leave the cursor in the
  414.              * correct position.  For example, a search for ")$"
  415.              * will leave the cursor at the end of the line, while
  416.              * a search for ")<NL>" will leave the cursor at the
  417.              * beginning of the next line.  This follows the
  418.              * notion that the meta-character '$' (and likewise
  419.              * '^') match positions, not characters.
  420.              */
  421.             if (mcptr->mc_type == BOL)
  422.                 if (curoff == llength(curline))
  423.                 {
  424.                     c = nextch(&curline, &curoff,
  425.                            direct ^ REVERSE);
  426.                     goto success;
  427.                 }
  428.                 else
  429.                     return FALSE;
  430.  
  431.             if (mcptr->mc_type == EOL)
  432.                 if (curoff == 0)
  433.                 {
  434.                     c = nextch(&curline, &curoff,
  435.                            direct ^ REVERSE);
  436.                     goto success;
  437.                 }
  438.                 else
  439.                     return FALSE;
  440.  
  441.             /* Neither BOL nor EOL, so go through
  442.              * the meta-character equal function.
  443.              */
  444.             if (!mceq(c, mcptr))
  445.                 return FALSE;
  446.         }
  447.  
  448.         /* Increment the length counter and
  449.          * advance the pattern pointer.
  450.          */
  451.         mclen++;
  452.         mcptr++;
  453.     }            /* End of mcptr loop.*/
  454.  
  455.     /* A SUCCESSFULL MATCH!!!
  456.      * Reset the "." pointers.
  457.      */
  458. success:
  459.     *pcwline = curline;
  460.     *pcwoff  = curoff;
  461.  
  462.     return TRUE;
  463. }
  464. #endif
  465.  
  466. /*
  467.  * scanner -- Search for a pattern in either direction.
  468.  */
  469. int    scanner(patrn, direct, beg_or_end)
  470. char    *patrn;        /* string to scan for */
  471. int    direct;        /* which way to go.*/
  472. int    beg_or_end;    /* put point at beginning or end of pattern.*/
  473. {
  474.     register int c;            /* character at current position */
  475.     register char *patptr;        /* pointer into pattern */
  476.     register LINE *lastline;    /* last line position during scan */
  477.     register int lastoff;        /* position within last line */
  478.     LINE *curline;            /* current line during scan */
  479.     int curoff;            /* position within current line */
  480.     LINE *matchline;        /* current line during matching */
  481.     int matchoff;            /* position in matching line */
  482.  
  483.     /* If we are going in reverse, then the 'end' is actually
  484.      * the beginning of the pattern.  Toggle it.
  485.      */
  486.     beg_or_end ^= direct;
  487.  
  488.     /* Setup local scan pointers to global ".".
  489.      */
  490.     curline = curwp->w_dotp;
  491.     curoff = curwp->w_doto;
  492.  
  493.     /* Scan each character until we hit the head link record.
  494.      */
  495.     while (!boundry(curline, curoff, direct))
  496.     {
  497.         /* Save the current position in case we need to
  498.          * restore it on a match.
  499.          */
  500.         lastline = curline;
  501.         lastoff = curoff;
  502.  
  503.         /* Get the character resolving newlines, and
  504.          * test it against first char in pattern.
  505.          */
  506.         c = nextch(&curline, &curoff, direct);
  507.  
  508.         if (eq(c, patrn[0]))    /* if we find it..*/
  509.         {
  510.             /* Setup match pointers.
  511.              */
  512.             matchline = curline;
  513.             matchoff = curoff;
  514.             patptr = &patrn[0];
  515.  
  516.             /* Scan through the pattern for a match.
  517.              */
  518.             while (*++patptr != '\0')
  519.             {
  520.                 c = nextch(&matchline, &matchoff, direct);
  521.  
  522.                 if (!eq(c, *patptr))
  523.                     goto fail;
  524.             }
  525.  
  526.             /* A SUCCESSFULL MATCH!!!
  527.              * reset the global "." pointers
  528.              */
  529.             if (beg_or_end == PTEND)    /* at end of string */
  530.             {
  531.                 curwp->w_dotp = matchline;
  532.                 curwp->w_doto = matchoff;
  533.             }
  534.             else        /* at beginning of string */
  535.             {
  536.                 curwp->w_dotp = lastline;
  537.                 curwp->w_doto = lastoff;
  538.             }
  539.  
  540.             curwp->w_flag |= WFMOVE; /* Flag that we have moved.*/
  541.             return TRUE;
  542.  
  543.         }
  544. fail:;            /* continue to search */
  545.     }
  546.  
  547.     return FALSE;    /* We could not find a match */
  548. }
  549.  
  550. /*
  551.  * eq -- Compare two characters.  The "bc" comes from the buffer, "pc"
  552.  *    from the pattern.  If we are not in EXACT mode, fold out the case.
  553.  */
  554. int    eq(bc, pc)
  555. register int    bc;
  556. register int    pc;
  557. {
  558.     if ((curwp->w_bufp->b_mode & MDEXACT) == 0)
  559.     {
  560.         if (islower(bc))
  561.             bc ^= DIFCASE;
  562.  
  563.         if (islower(pc))
  564.             pc ^= DIFCASE;
  565.     }
  566.  
  567.     return (bc == pc);
  568. }
  569.  
  570. /*
  571.  * readpattern -- Read a pattern.  Stash it in apat.  If it is the
  572.  *    search string, create the reverse pattern and the magic
  573.  *    pattern, assuming we are in MAGIC mode (and defined that way).
  574.  *    Apat is not updated if the user types in an empty line.  If
  575.  *    the user typed an empty line, and there is no old pattern, it is
  576.  *    an error.  Display the old pattern, in the style of Jeff Lomicka.
  577.  *    There is some do-it-yourself control expansion.  Change to using
  578.  *    <META> to delimit the end-of-pattern to allow <NL>s in the search
  579.  *    string. 
  580.  */
  581. static int    readpattern(prompt, apat, srch)
  582. char    *prompt;
  583. char    apat[];
  584. int    srch;
  585. {
  586.     int status;
  587.     char tpat[NPAT+20];
  588.  
  589.     strcpy(tpat, prompt);    /* copy prompt to output string */
  590.     strcat(tpat, " [");    /* build new prompt string */
  591.     expandp(&apat[0], &tpat[strlen(tpat)], NPAT/2);    /* add old pattern */
  592.     strcat(tpat, "]<META>: ");
  593.  
  594.     /* Read a pattern.  Either we get one,
  595.      * or we just get the META charater, and use the previous pattern.
  596.      * Then, if it's the search string, make a reversed pattern.
  597.      * *Then*, make the meta-pattern, if we are defined that way.
  598.      */
  599.     if ((status = mlreplyt(tpat, tpat, NPAT, metac)) == TRUE)
  600.     {
  601.         strcpy(apat, tpat);
  602.         if (srch)    /* If we are doing the search string.*/
  603.         {
  604.             /* Reverse string copy.
  605.              */
  606.             rvstrcpy(tap, apat);
  607. #if    MAGIC
  608.             /* Only make the meta-pattern if in magic mode,
  609.              * since the pattern in question might have an
  610.              * invalid meta combination.
  611.              */
  612.             if ((curwp->w_bufp->b_mode & MDMAGIC) == 0)
  613.                 mcpat[0].mc_type = tapcm[0].mc_type = MCNIL;
  614.             else
  615.                 status = mcstr();
  616. #endif
  617.         }
  618.     }
  619.     else if (status == FALSE && apat[0] != 0)    /* Old one */
  620.         status = TRUE;
  621.  
  622.     return(status);
  623. }
  624.  
  625. /*
  626.  * rvstrcpy -- Reverse string copy.
  627.  */
  628. rvstrcpy(rvstr, str)
  629. register char    *rvstr, *str;
  630. {
  631.     register int i;
  632.  
  633.     str += (i = strlen(str));
  634.  
  635.     while (i-- > 0)
  636.         *rvstr++ = *--str;
  637.  
  638.     *rvstr = '\0';
  639. }
  640.  
  641. /*
  642.  * sreplace -- Search and replace.
  643.  */
  644. sreplace(f, n)
  645. int f;        /* default flag */
  646. int n;        /* # of repetitions wanted */
  647. {
  648.     return(replaces(FALSE, f, n));
  649. }
  650.  
  651. /*
  652.  * qreplace -- search and replace with query.
  653.  */
  654. qreplace(f, n)
  655. int f;        /* default flag */
  656. int n;        /* # of repetitions wanted */
  657. {
  658.     return(replaces(TRUE, f, n));
  659. }
  660.  
  661. /*
  662.  * replaces -- Search for a string and replace it with another
  663.  *    string.  Query might be enabled (according to kind).
  664.  */
  665. static int    replaces(kind, f, n)
  666. int    kind;    /* Query enabled flag */
  667. int    f;    /* default flag */
  668. int    n;    /* # of repetitions wanted */
  669. {
  670.     register int i;        /* loop index */
  671.     register int status;    /* success flag on pattern inputs */
  672.     register int slength,
  673.              rlength;    /* length of search and replace strings */
  674.     register int numsub;    /* number of substitutions */
  675.     register int nummatch;    /* number of found matches */
  676.     int nlflag;        /* last char of search string a <NL>? */
  677.     int nlrepl;        /* was a replace done on the last line? */
  678.     char tmpc;        /* temporary character */
  679.     char c;            /* input char for query */
  680.     char tpat[NPAT];    /* temporary to hold search pattern */
  681.     LINE *origline;        /* original "." position */
  682.     int origoff;        /* and offset (for . query option) */
  683.     LINE *lastline;        /* position of last replace and */
  684.     int lastoff;        /* offset (for 'u' query option) */
  685.  
  686.     if (curbp->b_mode & MDVIEW)    /* don't allow this command if    */
  687.         return(rdonly());    /* we are in read only mode    */
  688.  
  689.     /* Check for negative repetitions.
  690.      */
  691.     if (f && n < 0)
  692.         return(FALSE);
  693.  
  694.     /* Ask the user for the text of a pattern.
  695.      */
  696.     if ((status = readpattern(
  697.         (kind == FALSE ? "Replace" : "Query replace"), &pat[0], TRUE))
  698.                                 != TRUE)
  699.         return(status);
  700.  
  701.     /* Ask for the replacement string.
  702.      */
  703.     if ((status = readpattern("with", &rpat[0], FALSE)) == ABORT)
  704.         return(status);
  705.  
  706.     /* Find the lengths of the strings.
  707.      */
  708.     slength = strlen(&pat[0]);
  709.     rlength = strlen(&rpat[0]);
  710.  
  711.     /* Set up flags so we can make sure not to do a recursive
  712.      * replace on the last line.
  713.      */
  714.     nlflag = (pat[slength - 1] == '\n');
  715.     nlrepl = FALSE;
  716.  
  717.     if (kind)
  718.     {
  719.         /* Build query replace question string.
  720.          */
  721.         strcpy(tpat, "Replace '");
  722.         expandp(&pat[0], &tpat[strlen(tpat)], NPAT/3);
  723.         strcat(tpat, "' with '");
  724.         expandp(&rpat[0], &tpat[strlen(tpat)], NPAT/3);
  725.         strcat(tpat, "'? ");
  726.  
  727.         /* Initialize last replaced pointers.
  728.          */
  729.         lastline = NULL;
  730.         lastoff = 0;
  731.     }
  732.  
  733.     /* Save original . position, init the number of matches and
  734.      * substitutions, and scan through the file.
  735.      */
  736.     origline = curwp->w_dotp;
  737.     origoff = curwp->w_doto;
  738.     numsub = 0;
  739.     nummatch = 0;
  740.  
  741.     while ( (f == FALSE || n > nummatch) &&
  742.         (nlflag == FALSE || nlrepl == FALSE) )
  743.     {
  744.         /* Search for the pattern.
  745.          * If we search with a regular expression, also save
  746.          * the true length of matched string.
  747.          */
  748. #if    MAGIC
  749.         if ((magical && curwp->w_bufp->b_mode & MDMAGIC) != 0)
  750.         {
  751.             if (!mcscanner(&mcpat[0], FORWARD, PTBEG))
  752.                 break;
  753.             slength = mclen;
  754.         }
  755.         else
  756. #endif
  757.             if (!scanner(&pat[0], FORWARD, PTBEG))
  758.                 break;        /* all done */
  759.  
  760.         ++nummatch;    /* Increment # of matches */
  761.  
  762.         /* Check if we are on the last line.
  763.          */
  764.         nlrepl = (lforw(curwp->w_dotp) == curwp->w_bufp->b_linep);
  765.  
  766.         /* Check for query.
  767.          */
  768.         if (kind)
  769.         {
  770.             /* Get the query.
  771.              */
  772. pprompt:        mlwrite(&tpat[0], &pat[0], &rpat[0]);
  773. qprompt:
  774.             update();  /* show the proposed place to change */
  775.             c = tgetc();            /* and input */
  776.             mlwrite("");            /* and clear it */
  777.  
  778.             /* And respond appropriately.
  779.              */
  780.             switch (c)
  781.             {
  782.                 case 'y':    /* yes, substitute */
  783.                 case ' ':
  784.                     break;
  785.  
  786.                 case 'n':    /* no, onword */
  787.                     forwchar(FALSE, 1);
  788.                     continue;
  789.  
  790.                 case '!':    /* yes/stop asking */
  791.                     kind = FALSE;
  792.                     break;
  793.  
  794.                 case 'u':    /* undo last and re-prompt */
  795.  
  796.                     /* Restore old position.
  797.                      */
  798.                     if (lastline == NULL)
  799.                     {
  800.                         /* There is nothing to undo.
  801.                          */
  802.                         TTbeep();
  803.                         goto qprompt;
  804.                     }
  805.                     curwp->w_dotp = lastline;
  806.                     curwp->w_doto = lastoff;
  807.                     lastline = NULL;
  808.                     lastoff = 0;
  809.  
  810.                     /* Delete the new string.
  811.                      */
  812.                     backchar(FALSE, rlength);
  813.                     if (!ldelete(rlength, FALSE))
  814.                     {
  815.                         mlwrite("%%ERROR while deleting");
  816.                         return(FALSE);
  817.                     }
  818.  
  819.                     /* And put in the old one.
  820.                      */
  821.                     for (i = 0; i < slength; i++)
  822.                     {
  823.                         tmpc = pat[i];
  824.                         status = (tmpc == '\n'?
  825.                             lnewline():
  826.                             linsert(1, tmpc));
  827.  
  828.                         /* Insertion error?
  829.                          */
  830.                         if (!status)
  831.                         {
  832.                             mlwrite("%%Out of memory while inserting");
  833.                             return(FALSE);
  834.                         }
  835.                     }
  836.  
  837.                     /* Record one less substitution,
  838.                      * backup, and reprompt.
  839.                      */
  840.                     --numsub;
  841.                     backchar(FALSE, slength);
  842.                     goto pprompt;
  843.  
  844.                 case '.':    /* abort! and return */
  845.                     /* restore old position */
  846.                     curwp->w_dotp = origline;
  847.                     curwp->w_doto = origoff;
  848.                     curwp->w_flag |= WFMOVE;
  849.  
  850.                 case BELL:    /* abort! and stay */
  851.                     mlwrite("Aborted!");
  852.                     return(FALSE);
  853.  
  854.                 default:    /* bitch and beep */
  855.                     TTbeep();
  856.  
  857.                 case '?':    /* help me */
  858.                     mlwrite(
  859. "(Y)es, (N)o, (!)Do rest, (U)ndo last, (^G)Abort, (.)Abort back, (?)Help: ");
  860.                     goto qprompt;
  861.  
  862.             }    /* end of switch */
  863.         }    /* end of "if kind" */
  864.  
  865.         /*
  866.          * Delete the sucker.
  867.          */
  868.         if (!ldelete(slength, FALSE))
  869.         {
  870.             mlwrite("%%ERROR while deleteing");
  871.             return(FALSE);
  872.         }
  873.  
  874.         /* And insert its replacement.
  875.          */
  876.         for (i = 0; i < rlength; i++)
  877.         {
  878.             tmpc = rpat[i];
  879.             status = (tmpc == '\n'? lnewline(): linsert(1, tmpc));
  880.  
  881.             /* Insertion error?
  882.              */
  883.             if (!status)
  884.             {
  885.                 mlwrite("%%Out of memory while inserting");
  886.                 return(FALSE);
  887.             }
  888.         }
  889.  
  890.         /* Save where we are if we might undo this....
  891.          */
  892.         if (kind)
  893.         {
  894.             lastline = curwp->w_dotp;
  895.             lastoff = curwp->w_doto;
  896.         }
  897.  
  898.         numsub++;    /* increment # of substitutions */
  899.     }
  900.  
  901.     /* And report the results.
  902.      */
  903.     mlwrite("%d substitutions", numsub);
  904.     return(TRUE);
  905. }
  906.  
  907. /*
  908.  * expandp -- Expand control key sequences for output.
  909.  */
  910. expandp(srcstr, deststr, maxlength)
  911. char *srcstr;    /* string to expand */
  912. char *deststr;    /* destination of expanded string */
  913. int maxlength;    /* maximum chars in destination */
  914. {
  915.     char c;        /* current char to translate */
  916.  
  917.     /* Scan through the string.
  918.      */
  919.     while ((c = *srcstr++) != 0)
  920.     {
  921.         if (c == '\n')        /* it's a newline */
  922.         {
  923.             *deststr++ = '<';
  924.             *deststr++ = 'N';
  925.             *deststr++ = 'L';
  926.             *deststr++ = '>';
  927.             maxlength -= 4;
  928.         }
  929.         else if (c < 0x20 || c == 0x7f)    /* control character */
  930.         {
  931.             *deststr++ = '^';
  932.             *deststr++ = c ^ 0x40;
  933.             maxlength -= 2;
  934.         }
  935.         else if (c == '%')
  936.         {
  937.             *deststr++ = '%';
  938.             *deststr++ = '%';
  939.             maxlength -= 2;
  940.         }
  941.         else            /* any other character */
  942.         {
  943.             *deststr++ = c;
  944.             maxlength--;
  945.         }
  946.  
  947.         /* check for maxlength */
  948.         if (maxlength < 4)
  949.         {
  950.             *deststr++ = '$';
  951.             *deststr = '\0';
  952.             return(FALSE);
  953.         }
  954.     }
  955.     *deststr = '\0';
  956.     return(TRUE);
  957. }
  958.  
  959. /*
  960.  * boundry -- Return information depending on whether we may search no
  961.  *    further.  Beginning of file and end of file are the obvious
  962.  *    cases, but we may want to add further optional boundry restrictions
  963.  *    in future, a' la VMS EDT.  At the moment, just return TRUE or
  964.  *    FALSE depending on if a boundry is hit (ouch).
  965.  */
  966. int    boundry(curline, curoff, dir)
  967. LINE    *curline;
  968. int    curoff, dir;
  969. {
  970.     register int    border;
  971.  
  972.     if (dir == FORWARD)
  973.     {
  974.         border = (curoff == llength(curline)) &&
  975.              (lforw(curline) == curbp->b_linep);
  976.     }
  977.     else
  978.     {
  979.         border = (curoff == 0) &&
  980.              (lback(curline) == curbp->b_linep);
  981.     }
  982.     return (border);
  983. }
  984.  
  985. /*
  986.  * nextch -- retrieve the next/previous character in the buffer,
  987.  *    and advance/retreat the point.
  988.  *    The order in which this is done is significant, and depends
  989.  *    upon the direction of the search.  Forward searches look at
  990.  *    the current character and move, reverse searches move and
  991.  *    look at the character.
  992.  */
  993. static int    nextch(pcurline, pcuroff, dir)
  994. LINE    **pcurline;
  995. int    *pcuroff;
  996. int    dir;
  997. {
  998.     register LINE    *curline;
  999.     register int    curoff;
  1000.     register int    c;
  1001.  
  1002.     curline = *pcurline;
  1003.     curoff = *pcuroff;
  1004.  
  1005.     if (dir == FORWARD)
  1006.     {
  1007.         if (curoff == llength(curline))        /* if at EOL */
  1008.         {
  1009.             curline = lforw(curline);    /* skip to next line */
  1010.             curoff = 0;
  1011.             c = '\n';            /* and return a <NL> */
  1012.         }
  1013.         else
  1014.             c = lgetc(curline, curoff++);    /* get the char */
  1015.     }
  1016.     else            /* Reverse.*/
  1017.     {
  1018.         if (curoff == 0)
  1019.         {
  1020.             curline = lback(curline);
  1021.             curoff = llength(curline);
  1022.             c = '\n';
  1023.         }
  1024.         else
  1025.             c = lgetc(curline, --curoff);
  1026.  
  1027.     }
  1028.     *pcurline = curline;
  1029.     *pcuroff = curoff;
  1030.  
  1031.     return (c);
  1032. }
  1033.  
  1034. #if    MAGIC
  1035. /*
  1036.  * mcstr -- Set up the 'magic' array.  The closure symbol is taken as
  1037.  *    a literal character when (1) it is the first character in the
  1038.  *    pattern, and (2) when preceded by a symbol that does not allow
  1039.  *    closure, such as a newline, beginning of line symbol, or another
  1040.  *    closure symbol.
  1041.  *
  1042.  *    Coding comment (jmg):  yes, i know i have gotos that are, strictly
  1043.  *    speaking, unnecessary.  But right now we are so cramped for
  1044.  *    code space that i will grab what i can in order to remain
  1045.  *    within the 64K limit.  C compilers actually do very little
  1046.  *    in the way of optimizing - they expect you to do that.
  1047.  */
  1048. static int    mcstr()
  1049. {
  1050.     MC    *mcptr, *rtpcm;
  1051.     char    *patptr;
  1052.      int    mj;
  1053.      int    pchr;
  1054.      int    status = TRUE;
  1055.      int    does_closure = FALSE;
  1056.  
  1057.     /* If we had metacharacters in the MC array previously,
  1058.      * free up any bitmaps that may have been allocated.
  1059.      */
  1060.     if (magical)
  1061.         freebits();
  1062.  
  1063.     magical = FALSE;
  1064.     mj = 0;
  1065.     mcptr = &mcpat[0];
  1066.     patptr = &pat[0];
  1067.  
  1068.     while ((pchr = *patptr) && status)
  1069.     {
  1070.         switch (pchr)
  1071.         {
  1072.             case MC_CCL:
  1073.                 status = cclmake(&patptr, mcptr);
  1074.                 magical = TRUE;
  1075.                 does_closure = TRUE;
  1076.                 break;
  1077.             case MC_BOL:
  1078.                 if (mj != 0)
  1079.                     goto litcase;
  1080.  
  1081.                 mcptr->mc_type = BOL;
  1082.                 magical = TRUE;
  1083.                 does_closure = FALSE;
  1084.                 break;
  1085.             case MC_EOL:
  1086.                 if (*(patptr + 1) != '\0')
  1087.                     goto litcase;
  1088.  
  1089.                 mcptr->mc_type = EOL;
  1090.                 magical = TRUE;
  1091.                 does_closure = FALSE;
  1092.                 break;
  1093.             case MC_ANY:
  1094.                 mcptr->mc_type = ANY;
  1095.                 magical = TRUE;
  1096.                 does_closure = TRUE;
  1097.                 break;
  1098.             case MC_CLOSURE:
  1099.                 /* Does the closure symbol mean closure here?
  1100.                  * If so, back up to the previous element
  1101.                  * and indicate it is enclosed.
  1102.                  */
  1103.                 if (!does_closure)
  1104.                     goto litcase;
  1105.                 mj--;
  1106.                 mcptr--;
  1107.                 mcptr->mc_type |= CLOSURE;
  1108.                 magical = TRUE;
  1109.                 does_closure = FALSE;
  1110.                 break;
  1111.  
  1112.             /* Note: no break between MC_ESC case and the default.
  1113.              */
  1114.             case MC_ESC:
  1115.                 if (*(patptr + 1) != '\0')
  1116.                 {
  1117.                     pchr = *++patptr;
  1118.                     magical = TRUE;
  1119.                 }
  1120.             default:
  1121. litcase:            mcptr->mc_type = LITCHAR;
  1122.                 mcptr->u.lchar = pchr;
  1123.                 does_closure = (pchr != '\n');
  1124.                 break;
  1125.         }        /* End of switch.*/
  1126.         mcptr++;
  1127.         patptr++;
  1128.         mj++;
  1129.     }        /* End of while.*/
  1130.  
  1131.     /* Close off the meta-string.
  1132.      */
  1133.     mcptr->mc_type = MCNIL;
  1134.  
  1135.     /* Set up the reverse array, if the status is good.  Please note the
  1136.      * structure assignment - your compiler may not like that.
  1137.      * If the status is not good, nil out the meta-pattern.
  1138.      * The only way the status would be bad is from the cclmake()
  1139.      * routine, and the bitmap for that member is guarenteed to be
  1140.      * freed.  So we stomp a MCNIL value there, call freebits() to
  1141.      * free any other bitmaps, and set the zeroth array to MCNIL.
  1142.      */
  1143.     if (status)
  1144.     {
  1145.         rtpcm = &tapcm[0];
  1146.         while (--mj >= 0)
  1147.         {
  1148. #if    LATTICE
  1149.             movmem(--mcptr, rtpcm++, sizeof (MC));
  1150. #endif
  1151.  
  1152. #if    MWC86 | AZTEC | MSC | VMS | USG | BSD | V7
  1153.             *rtpcm++ = *--mcptr;
  1154. #endif
  1155.         }
  1156.         rtpcm->mc_type = MCNIL;
  1157.     }
  1158.     else
  1159.     {
  1160.         (--mcptr)->mc_type = MCNIL;
  1161.         freebits();
  1162.         mcpat[0].mc_type = tapcm[0].mc_type = MCNIL;
  1163.     }
  1164.  
  1165.     return(status);
  1166. }
  1167.  
  1168. /*
  1169.  * mceq -- meta-character equality with a character.  In Kernighan & Plauger's
  1170.  *    Software Tools, this is the function omatch(), but i felt there
  1171.  *    were too many functions with the 'match' name already.
  1172.  */
  1173. static int    mceq(bc, mt)
  1174. int    bc;
  1175. MC    *mt;
  1176. {
  1177.     register int result;
  1178.  
  1179.     switch (mt->mc_type & MASKCL)
  1180.     {
  1181.         case LITCHAR:
  1182.             result = eq(bc, mt->u.lchar);
  1183.             break;
  1184.  
  1185.         case ANY:
  1186.             result = (bc != '\n');
  1187.             break;
  1188.  
  1189.         case CCL:
  1190.             if (!(result = biteq(bc, mt->u.cclmap)))
  1191.             {
  1192.                 if ((curwp->w_bufp->b_mode & MDEXACT) == 0 &&
  1193.                     (isletter(bc)))
  1194.                 {
  1195.                     result = biteq(CHCASE(bc), mt->u.cclmap);
  1196.                 }
  1197.             }
  1198.             break;
  1199.  
  1200.         case NCCL:
  1201.             result = !biteq(bc, mt->u.cclmap);
  1202.  
  1203.             if ((curwp->w_bufp->b_mode & MDEXACT) == 0 &&
  1204.                 (isletter(bc)))
  1205.             {
  1206.                 result &= !biteq(CHCASE(bc), mt->u.cclmap);
  1207.             }
  1208.             break;
  1209.  
  1210.         default:
  1211.             mlwrite("mceq: what is %d?", mt->mc_type);
  1212.             result = FALSE;
  1213.             break;
  1214.  
  1215.     }    /* End of switch.*/
  1216.  
  1217.     return (result);
  1218. }
  1219.  
  1220. /*
  1221.  * cclmake -- create the bitmap for the character class.
  1222.  *    ppatptr is left pointing to the end-of-character-class character,
  1223.  *    so that a loop may automatically increment with safety.
  1224.  */
  1225. static int    cclmake(ppatptr, mcptr)
  1226. char    **ppatptr;
  1227. MC    *mcptr;
  1228. {
  1229.     BITMAP        clearbits();
  1230.     BITMAP        bmap;
  1231.     register char    *patptr;
  1232.     register int    pchr, ochr;
  1233.  
  1234.     if ((bmap = clearbits()) == NULL)
  1235.     {
  1236.         mlwrite("%%Out of memory");
  1237.         return FALSE;
  1238.     }
  1239.  
  1240.     mcptr->u.cclmap = bmap;
  1241.     patptr = *ppatptr;
  1242.  
  1243.     /*
  1244.      * Test the initial character(s) in ccl for
  1245.      * special cases - negate ccl, or an end ccl
  1246.      * character as a first character.  Anything
  1247.      * else gets set in the bitmap.
  1248.      */
  1249.     if (*++patptr == MC_NCCL)
  1250.     {
  1251.         patptr++;
  1252.         mcptr->mc_type = NCCL;
  1253.     }
  1254.     else
  1255.         mcptr->mc_type = CCL;
  1256.  
  1257.     if ((ochr = *patptr) == MC_ECCL)
  1258.     {
  1259.         mlwrite("%%No characters in character class");
  1260.         return (FALSE);
  1261.     }
  1262.     else
  1263.     {
  1264.         if (ochr == MC_ESC)
  1265.             ochr = *++patptr;
  1266.  
  1267.         setbit(ochr, bmap);
  1268.         patptr++;
  1269.     }
  1270.  
  1271.     while (ochr != '\0' && (pchr = *patptr) != MC_ECCL)
  1272.     {
  1273.         switch (pchr)
  1274.         {
  1275.             /* Range character loses its meaning
  1276.              * if it is the last character in
  1277.              * the class.
  1278.              */
  1279.             case MC_RCCL:
  1280.                 if (*(patptr + 1) == MC_ECCL)
  1281.                     setbit(pchr, bmap);
  1282.                 else
  1283.                 {
  1284.                     pchr = *++patptr;
  1285.                     while (++ochr <= pchr)
  1286.                         setbit(ochr, bmap);
  1287.                 }
  1288.                 break;
  1289.  
  1290.             /* Note: no break between case MC_ESC and the default.
  1291.              */
  1292.             case MC_ESC:
  1293.                 pchr = *++patptr;
  1294.             default:
  1295.                 setbit(pchr, bmap);
  1296.                 break;
  1297.         }
  1298.         patptr++;
  1299.         ochr = pchr;
  1300.     }
  1301.  
  1302.     *ppatptr = patptr;
  1303.  
  1304.     if (ochr == '\0')
  1305.     {
  1306.         mlwrite("%%Character class not ended");
  1307.         free(bmap);
  1308.         return FALSE;
  1309.     }
  1310.     return TRUE;
  1311. }
  1312.  
  1313. /*
  1314.  * biteq -- is the character in the bitmap?
  1315.  */
  1316. static int    biteq(bc, cclmap)
  1317. int    bc;
  1318. BITMAP    cclmap;
  1319. {
  1320.     if (bc >= HICHAR)
  1321.         return FALSE;
  1322.  
  1323.     return( (*(cclmap + (bc >> 3)) & BIT(bc & 7))? TRUE: FALSE );
  1324. }
  1325.  
  1326. /*
  1327.  * clearbits -- Allocate and zero out a CCL bitmap.
  1328.  */
  1329. static    BITMAP clearbits()
  1330. {
  1331.     char        *malloc();
  1332.  
  1333.     BITMAP        cclstart, cclmap;
  1334.     register int    j;
  1335.  
  1336.     if ((cclmap = cclstart = (BITMAP) malloc(HIBYTE)) != NULL)
  1337.         for (j = 0; j < HIBYTE; j++)
  1338.             *cclmap++ = 0;
  1339.  
  1340.     return (cclstart);
  1341. }
  1342.  
  1343. /*
  1344.  * freebits -- Free up any CCL bitmaps.
  1345.  */
  1346. static    freebits()
  1347. {
  1348.     register MC    *mcptr;
  1349.  
  1350.     mcptr = &mcpat[0];
  1351.  
  1352.     while (mcptr->mc_type != MCNIL)
  1353.     {
  1354.         if ((mcptr->mc_type & MASKCL) == CCL ||
  1355.             (mcptr->mc_type & MASKCL) == NCCL)
  1356.             free(mcptr->u.cclmap);
  1357.         mcptr++;
  1358.     }
  1359. }
  1360.  
  1361. /*
  1362.  * setbit -- Set a bit (ON only) in the bitmap.
  1363.  */
  1364. static    setbit(bc, cclmap)
  1365. int    bc;
  1366. BITMAP    cclmap;
  1367. {
  1368.     if (bc < HICHAR)
  1369.         *(cclmap + (bc >> 3)) |= BIT(bc & 7);
  1370. }
  1371. #endif
  1372.